package algorithm.linear;

/**
 * 判断括号匹配的算法
 */
public class Exp_bracket {
    //判断expstr表达式中的圆括号是否匹配，返回错误信息
    public static String isValid(String expstr){
        SeqStack<String> stack = new SeqStack<String>(expstr.length());
        int i = 0;
        while( i < expstr.length() ) {
            char ch = expstr.charAt(i);
            i++;
            switch (ch){
                case '(':
                    //左括号入栈
                    stack.push( ch+"");
                    break;
                case ')':
                    //遇见右括号时，出栈
                    //System.out.println(stack.pop());
                    if (stack.isEmpty() || !stack.pop().equals("("))
                        return "期望(";
            }
        }
        if (stack.isEmpty()) {
            return "";
        } else {
            System.out.println(stack.toString());
            return "期望)";
        }
    }

    public static void main(String[] args) {
        String expstr = "((1+2)*3+4)";
        System.out.println(expstr+" -> "+ isValid(expstr));

        String expstr1 = "((1+2)*3+4";
        System.out.println(expstr1+" -> "+ isValid(expstr1));

        String expstr2 = "((1+2)*3+4))";
        System.out.println(expstr2+" -> "+ isValid(expstr2));
    }
}
